#include <stdio.h>
#include <stdint.h>
/*
template<typename T> T gcd(T a, T b){ return b?gcd(b,a%b):a; }
template<typename T> T fun(T a, T b){T c=gcd(a,b);return c>1?fun(a/c,b):a;}
*/
int64_t gcd(int64_t a, int64_t b){ return b?gcd(b,a%b):a; }
int64_t fun(int64_t a, int64_t b){int64_t c=gcd(a,b);return c>1?fun(a/c,b):a;}

int main(int argc, char **argv)
{
        int ncase;
        scanf("%d",&ncase);
        for(int icase=0;icase<ncase;icase++)
        {
            int64_t a,b;
           // cin >>a>>b;
            scanf("%I64d%I64d", &a,&b);
            //cout<<"Case #"<<(icase+1)<<": "<<(fun(a,b)==1?"YES":"NO");
            //if(icase!=ncase-1)cout <<"\n";
            //else cout << endl;
            printf("Case #%d: %s\n", icase+1, fun(a,b)==1?"YES":"NO");
        }
        return 0;
}
